As is known in the art, Orthogonal Frequency Division Multiple Access (OFDMA) is a multi-user version of the popular OFDM digital modulation scheme. Multiple access is achieved in OFDMA by assigning subsets of subcarriers to individual users. This allows simultaneous low data rate transmission from several users.
More particularly, FIG. 1 illustrates the OFDMA frame structure for a Time Division Duplex (TDD) implementation. Each frame is divided by downlink (DL) and uplink (UL) sub-frames with the separation of Transmit/Receive (TTG) and Receive/Transmit (RTG) Transition Gaps to avoid DL and UL transmission collisions, see “Mobile WiMAX—Part I: A Technical Overview and Performance Evaluation,” WiMAX Forum, March 2006. The Media Access Control (MAC) data should be mapped to an OFDMA data region for DL and UL using the procedure described in the FIG. 2.
More particularly, the data region in a sub frame is a rectangular shaped region having along one dimension, for example a bottom or width dimension of the rectangle, OFDMA symbol number spanning over time and having along an orthogonal dimension, for example a vertical or height dimension of the rectangle, logical sub channel number spanning over frequency. Each burst is mapped into a sub region of the data region. Each burst has at least one slot. A slot is the minimum possible data allocation region and it requires one sub-channel in frequency and one symbol in time. For simplicity each dimension may be referenced by the term “units” without explicit mention of sub-channels or time symbols, as this distinction is only used when describing orientation of the sub frame's data region in the examples. A slot is thus a rectangular region with dimensions one unit in the width dimension and one unit in the height dimension.
The UL mapping consists of two steps and is quite straightforward, see IEEE Std 802.16e, IEEE Standard for Local and Metropolitan Area Networks, Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access System, 2005 incorporated herein by reference. First, the data region in the UL sub-frame is selected for each burst. The first slot of the data region starts from the next slot of the last occupied slot and the selection is continued such that the OFDMA symbol index is increased. When the edge of the UL zone is reached, it is continued from the lowest numbered OFDMA symbol in the next available sub-channel. Once the slots are selected for the data region, the burst is mapped. The burst mapping within the UL allocation starts from the lowest numbered sub-channel in the lowest numbered OFDMA symbol and is continued such that the sub-channel index is increased.
More particularly, the UL burst allocation is well defined in 802.16e OFDMA standard and there is no need to further optimize the performance, see IEEE Std 802.16, IEEE Standard for Local and metropolitan area networks, Part 16: Air Interface for Fixed Broadband Wireless Access Systems, 2004 and IEEE Std 802.16e, IEEE Standard for Local and metropolitan area networks, Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access System, 2005.
On the contrary, the burst allocation problem in the DL sub-frame is a very challenging problem and it affects MAC performance of 802.16e OFDMA significantly. Here again, each down link sub frame includes a rectangular shaped data region having along one dimension, for example a bottom or width dimension of the rectangle, OFDMA symbol number in time and having along an orthogonal; dimension, for example a vertical or height dimension of the rectangle, logical sub channel number in frequency. Further, the DL-burst for data transmission requires a certain integer number of slots and it is mapped into a sub region of the data region that contains more slots than (or an equal number of slots to) the number of slots required by the burst. As noted above, a slot is the minimum possible data allocation unit. For example, in FIGS. 1-2, a slot is defined in IEEE 802.16 as one sub-channel in frequency and two OFDMA symbols in time in the DL subframe, and similarly a slot is defined as one sub-channel in frequency and three OFDMA symbols in time in the UL subframe. For simplicity in description, henceforth we shall consider a slot to be one sub-channel in frequency and one symbol in time. The allocated region for the burst is defined as a rectangular shaped sub region in a DL sub-frame since each Information Element (IE) for the burst in the DL-MAP contains symbol offset, sub-channel offset, number of symbols, and number of sub-channels, all of which are integer-valued. The sub region must be large enough to contain the burst. Otherwise the burst cannot be mapped into the sub region. The DL burst allocation problem is, therefore, the pre-allocation problem of the rectangular regions with integer dimensions in the DL sub-frame without overlapping. It should be noted that the burst must retain a rectangular shape (i.e., one dimension of the rectangle being OFDMA symbol number and another dimension of the rectangle being logical sub channel number), with each dimension having integer values, when allocated into the rectangular data region of the downlink sub frame.
There are two kinds of wasted slots in the DL burst allocation. Since the allocated sub region for the burst can be larger than the burst, there may be unused slots within this sub region. In addition, there are unallocated slots in the DL sub-frame because the rectangular shapes of the sub regions may not fill the sub-frame in its entirety. These wasted slots reduce the DL throughput and should be minimized. The optimal solution which minimizes the number of wasted slots and puts as many data bursts as possible in the sub-frame is not known to our best knowledge since it is a Nondeterministic Polynomial-time hard (NP-hard) problem.
Therefore, the DL-burst allocation is complicated because the data region for the burst is a two-dimensional allocation of a group of contiguous sub-channels in frequency, in a group of contiguous OFDMA symbols in time. This allocation may be visualized as a rectangle shown in FIG. 1 and requires a method, to solve how to allocate the data region within the sub-frame efficiently. Otherwise this allocation with a rectangle might degrade MAC throughput performance by generating too many wasted slots.
The DL-rectangular shaped burst allocation problem is, therefore, to allocate the data region within the DL sub-frame while minimizing the number of wasted slots. There are two kinds of wasted slots in the burst allocation as shown in FIG. 3. The total number of slots available in the rectangular allocated region for a burst should be more than (or equal to) the size of the burst and there might be unused slots within this allocated region. Another type of wasted slot is the unallocated slot. After the sub regions are mapped for all bursts into the sub-frame, there are some slots left in the sub-frame outside the sub regions. There exist these unallocated slots because either there are no more bursts to allocate or there are not enough slots left for another burst. These unallocated slots might be scattered in the DL sub-frame depending on the mapping method.
The optimal solution, which minimizes the total number of wasted slots while allocating as many bursts as possible, is not known (it is NP-hard). Instead of looking for the optimal solution, three methods in accordance with the inventions are provided based on myopic local optimization; one is referred to herein as a Bottom-Left (BL) method, a second one is referred to herein as a Large-Bottom-Priority (LBP) method; and the third is referred to herein as a Best-Fit (BF) level method. For a given burst, these three methods generate potential sub regions in the DL sub-frame, chooses a sub region that gives the minimum number of unused slots, and allocates the burst into this chosen sub region. If a burst cannot fit into the remaining unallocated slots, the method skips this burst and proceeds to the next burst. The method continues until the list of bursts is exhausted. These methods generally allocate the data region from the bottom-left (the first symbol) to the top-right (the last symbol). For BL and LBP, unallocated slots are at the top of the sub-frame and there are no unallocated slots in the middle. For BF, unallocated slots may appear in the middle of the sub-frame.
In accordance with the invention, a method is provided for allocating bursts into a region. The method includes: performing, for each one of the bursts, a series of trial mappings and determining the number of unused slots for each one of the trial mapping; and mapping, for each one of the bursts, a selected one of the trial mappings with the minimum number of unused slots into an unallocated portion of the region.
In one embodiment, the region is rectangular and wherein the mapping commences in a corner of the region.
In one embodiment, the method includes packing by choosing a location at a first corner of the region, attempting to place a burst using different sizes along one axis of the region, and choosing the largest one of the sizes having the minimum number of slots.
In one embodiment, if no placement is possible at a given corner because no valid trial mappings exist, the method proceeds to another corner of the region.
In one embodiment, the method includes packing by choosing a first size along an axis of the region in which the burst of that first size has at least one valid placement in the data region. In one embodiment, the method includes packing by choosing dimensions of the burst, from largest size along the first axis to smallest size along the first axis and terminating the trial mappings once the number of unused slots increases with a smaller size along the first axis.
In one embodiment, the trial mappings selection is in accordance with the minimum number of unused slots.
In one embodiment, the data region comprises a plurality of contiguous rectangular strips, each one of the strips having the same predetermined number of slots and wherein each one of the sub regions is made up of a portion of one or more contiguous ones of the strips and wherein the method places the burst in the narrowest one of the sub regions.
In one embodiment, the method includes constructing horizontal strips in the region and wherein the method finds trial mappings for each one of the horizontal strips and selects the trial mapping resulting in the minimum number of unused slots.
In one embodiment a method is provided for allocating bursts into sub regions of a fixed dimension data region. The method includes: determining, for each one of the bursts, potential positions and dimensions for the sub regions within the data region for allocation of the burst; and, selecting, for each one of the bursts, one of the potential sub regions resulting in the minimum number of unused slots for such one of the bursts.
In one embodiment, a method is provided for allocation downlink bursts in a data region of a OFDMA data system, e.g., an IEEE 802.16 data system, such data region having along one axis thereof increasing logical sub channel numbers and along another axis thereof increasing OFDMA symbol numbers, and wherein the burst are allocated into rectangular shaped sub regions within the data region.
In one embodiment, a method is provided for allocating downlink bursts into a data region of an OFDMA data system, such data region having along one axis thereof increasing logical sub channel numbers and along another axis thereof increasing OFDMA symbol numbers. The method includes mapping each one of the bursts into slots of a corresponding one of a plurality of contiguous rectangular shaped sub regions of the data region with each one of the sub regions having a minimum number of unused slots.
In one embodiment, the data region comprises a plurality of contiguous rectangular strips, each one of the strips having the same predetermined number of slots and wherein each one of the sub regions is made up of a portion of one or more contiguous ones of the strips.
In one embodiment, the mapping commences with a first one of the bursts being mapped at a corner of the data region.
In one embodiment, the corner is at the lowest logical sub channel number and the lowest OFDMA symbol number.
In one embodiment, a method is provided for allocating downlink bursts in a data region of an OFDMA data system, such data region having along one axis thereof increasing logical sub channel numbers and along another axis thereof increasing OFDMA symbol numbers. The method includes: dividing the data region into a plurality of contiguous rectangular strips along one of the axis with each one of the strips having the same predetermined number of slots; performing, for each one of the bursts, a series of trial mappings of such one of the bursts into a one or more of the contiguous vertical strips and determining the number of unused slots for each one of the trial mapping; and mapping such one of the bursts into slots of the one or more of the vertical strips having the minimum number of unused slots.
In one embodiment, when there are more than one trial mappings resulting in the minimum number of unused slots, the method maps the burst across the one of the trial mapping requiring the largest number of vertical strips.
In one embodiment, the method allocates the bursts into rectangular shaped sub regions of the data region with minimum unused sub regions within the data region. In one embodiment, the method creates and locates the data region with minimum unused slots at the lowest logical sub channel number and the lowest OFDMA symbol number.
In another embodiment, the method allocates the bursts within a data region having the largest size along one of the axes and then reduces the size along such axis only when the sub region with the smaller size along such axis has less number of unused slots.
In one embodiment a method is provided for allocating bursts into sub regions of a fixed dimension data region. The method includes: performing, for each one of the bursts, a series of trial mappings within levels within the region; performing, for each one of the bursts, a series of trial mappings creating a new level within the region; and mapping, for each one of the burst, a selected one of the trial mappings with the minimum number of unused slots into an unallocated portion of the data region. In one embodiment, the selected one of the trial mappings may be changed by fixing the length along one dimension and reducing the length along the other dimension.
In one embodiment, when there are more than one trial mappings resulting in the minimum number of unused slots, the method maps the burst across one of the trial mappings minimizing the remaining width within an existing level.
In one embodiment, when there are more than one trial mappings resulting in the minimum amount of remaining width in the level, the method maps the burst across one of the trial mappings with the least level height.
In one embodiment, when the current burst has no potential sub regions within any level, the method rearranges all previously-placed trial mappings by sorting the trial mappings within each level of the region in accordance with changes in height within the levels, and the method further sorts the trial allocations between levels of the region in accordance with the amount of used width for each level;
In one embodiment, the method performs trial allocations of the remaining bursts in accordance with the result of the sortings, and selecting, for each one of the remaining bursts, one of the potential sub regions resulting in the minimum number of unused slots for such one of the bursts.
In accordance with the invention, three heuristic methods are provided: the Bottom-Left (BL) method, the Large-Bottom-Priority (LBP) method, and the Best Fit level method referred above. The BL method allocates the data region at the bottom left point while minimizing the number of unused slots within the data region. That is, the basic idea of the BL is to allocate the data region at the bottom left point (lowest logical sub channel number and lowest OFDMA symbol) while minimizing the number of unused slots within the data region. The LBP method, on the other hand, operates by maintaining the largest bottom size available for future bursts, by also attempting to use smaller and smaller bottom sizes for the current burst, while keeping the number of unused slots for the burst minimized. The BF method packs bursts by using the concept of levels, or constant-height horizontal strips. Each burst is either packed into an existing level, or is placed into a new level. The heights of the levels are calculated dynamically depending on the input bursts, as well as on their order. None of these methods require any pre-defined vertical strips (i.e., vertical strips are defined by the number of slots along the horizontal direction; each vertical strip contains a certain number of slots along the horizontal direction and all slots along the vertical direction) beforehand and can handle the large bursts effectively.
Thus in accordance with one feature of the invention, a method is provided for allocation downlink bursts in a data region of a OFDMA data system, such data region having along one axis thereof increasing logical sub channel numbers and along another axis thereof increasing OFDMA symbol numbers, such method comprising: creating and locating the data region with minimum unused slots at the lowest logical sub channel number and the lowest OFDMA symbol number.
In accordance with another feature of the invention, a method for allocation downlink bursts in a data region of a OFDMA data system is provided, such data region having along one axis thereof increasing logical sub channel numbers and along another axis thereof increasing OFDMA symbol numbers. The method includes allocating the bursts within a data region having the largest size along one of the axes and then reduces the size along such one of the axes only when the data region with the smaller size along such one of the axes has less number of unused slots.
The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.
Like reference symbols in the various drawings indicate like elements.